"""
实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:
    -100.0 < x < 100.0
    n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
不论我们返回时候如何，我们执行第一步，先设立Base Case:
if b == 0: return 1

完了以后，我们要对大问题进行拆分，也就是不断的对b的值折半

拆分：
half = self.myPow(a, b // 2)

当拆分到了最小的问题，满足base case b == 0 的时候，我们则进行返回，返回时候有三种可能

Function的三种可能性：

当b为偶数的时候，比如 2 ^ 100，拆分的时候就变成 (2 ^ 50) * (2 ^ 50)
当b为基数的时候，比如 2 ^ 25，拆分的时候就变成  (2 ^12) * (2 ^ 12) * 2
当b为负数的时候，返回 1.0 / self.myPow(a, -b)

时间复杂度 = 一叉树里面每层的时间复杂度 * 层数 = 1 * log(b) = log(b)
空间复杂度 = O(h) 也就是一叉树的层数 = log(b)

"""


class Solution:
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n == 0: return 1
        if n < 0: return 1.0 / self.myPow(x, -n)
        half = self.myPow(x, n//2)
        if n % 2 == 0:
            return half * half
        else:
            return half * half * x
